# 第1节只有五行的算法——Floyd-Warshall
# 动态规划
e = [[0, 0, 0, 0, 0],
     [0, 0, 2, 6, 4],
     [0, 99, 0, 3, 99],
     [0, 7, 99, 0, 1],
     [0, 5, 99, 12, 0]
     ]

n = 4  # 顶点个数
m = 8  # 边个数
for k in (range(1, n + 1)):
    for i in (range(1, n + 1)):
        for j in (range(1, n + 1)):
            if e[i][j] > e[i][k] + e[k][j]:
                e[i][j] = e[i][k] + e[k][j]

# 输出最终结果
for i, v in enumerate(e):
    print(v)
